package com.learn.finished;
/*给你一个二元数组 nums ，和一个整数 goal ，请你统计并返回有多少个和为 goal 的非空子数组。

子数组 是数组的一段连续部分。

示例 1：

输入：nums = [1,0,1,0,1], goal = 2
输出：4
解释：
如下面黑体所示，有 4 个满足题目要求的子数组：
[1,0,1,0,1]
[1,0,1,0,1]
[1,0,1,0,1]
[1,0,1,0,1]
示例 2：

输入：nums = [0,0,0,0,0], goal = 0
输出：15

提示：

1 <= nums.length <= 3 * 104
nums[i] 不是 0 就是 1
0 <= goal <= nums.length
*/

import java.util.HashMap;
import java.util.Map;

public class num_930 {
    public static void main(String[] args) {
        System.out.println(numSubarraysWithSum(new int[]{1,0,1, 0, 1},2));
    }

    public static int numSubarraysWithSum(int[] nums, int goal) {
            int sum = 0;
            Map<Integer, Integer> cnt = new HashMap<Integer, Integer>();
            int ret = 0;
            for (int num : nums) {
                cnt.put(sum, cnt.getOrDefault(sum, 0) + 1);
                //0或者1
                sum += num;
                //sum-goal?
                ret += cnt.getOrDefault(sum - goal, 0);
            }
            return ret;
    }
}

